`
https://leetcode.cn/problems/last-stone-weight-ii/
`

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
  // 相当于是把 stones 数组分成两个子集，使得两个子集的重量差最小
  // 这样就转换成子集背包问题了

  const n = stones.length
  const sum = stones.reduce((acc, cur) => acc + cur, 0)
  const halfSum = sum >> 1

  // 给定一个容量为 halfSum 的背包和若干石头 stones，问这个背包能够装下的最大重量是多少
  const dp = Array.from({ length: n + 1 }, () => new Array(halfSum + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    // 有一格的偏差，所以第 i 颗石头是 stone[i - 1]
    const curStone = stones[i - 1]
    for (let j = 0; j < halfSum + 1; j++) {
      if (j - curStone < 0) {
        // 当前石头装不进去，只能选择不装
        dp[i][j] = dp[i - 1][j]
        continue
      }
      // 不装 或 装进去
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - curStone] + curStone)
    }
  }

  // sum / 2 的容量下，能装的最大重量
  const maxWeight = dp[n][halfSum]

  return sum - maxWeight * 2
};